ПРИМЕНЕНИЕ МЕТОДА K-СРЕДНИХ В ЗАДАЧЕ ОЦЕНКИ ХАРАКТЕРИСТИК ПРОЦЕССА ДЛЯ ВЕБ-ПРИЛОЖЕНИЙ

Евстратов В.В., Ананьевский М.С. Применение метода K-средних в задаче оценки характеристик процесса для веб-приложений // Научно-технический вестник информационных технологий,механики и оптики. 2020.Т .20. № 5. С. 755–760. doi: 10.17586/2226-1494-2020-20-5-755-760

Предмет исследования. Исследованы подходы к решению задачи оценки характеристик процесса на примере задачи прогнозирования характеристик активности пользователей в компьютерных онлайн-играх. Рассмотрены методы машинного обучения и определены потенциальные преимущества алгоритмов кластеризации в применении к рассматриваемой задаче. Исследованы различные метрики качества алгоритмов кластеризации. Метод. На основе гипотезы, возникшей в ходе предварительного анализа данных о пользовательской активности, разработан подход к оценке характеристик процесса, использующий кластеризацию. Собраны данные об активности пользователей, для которых уже известны значения прогнозируемых характеристик. Каждый пользователь представлен в виде пары векторов: первый вектор составлен из его характеристик в первые дни активности, второй – из прогнозируемых характеристик. Векторы, представляющие пользователей в первые дни активности, используются в качестве обучающей выборки для алгоритма K-средних. За подбор параметра K отвечает специально разработанный функционал энтропийного вида, адекватный исследуемой задаче. Выделенным кластерам ставятся в соответствие усредненные по попавшим в них пользователям векторы прогнозируемых характеристик. Эти соответствия используются в качестве прогнозов характеристик для новых пользователей. Основные результаты. Предложен ориентированный на рассмотренный тип данных метод оценки качества кластеризации, позволяющий выбрать наиболее подходящее для целевой задачи число кластеров. Проведен численный эксперимент, демонстрирующий применимость разработанного метода. Практическая значимость. Применение предложенного подхода позволяет прогнозировать одновременно несколько характеристик пользователей компьютерных онлайн-игр, и, таким образом, решать различные прикладные задачи планирования и аналитики, возникающие в ходе разработки. Например, изложенный в статье метод был использован в задачах анализа окупаемости разработки новых игровых элементов и прогнозирования нагрузки на серверы с целью заблаговременного наращивания мощностей. Его преимуществами являются отсутствие необходимости экспертной разметки обучающей выборки и относительно невысокие требования к вычислительным мощностям – в силу низкой вычислительной сложности функционала качества для подбора гиперпараметра K.

1. Zhang Z., Lai Z., Xu Y., Shao L., Wu J., Xie G.-S. Discriminative elastic-net regularized linear regression // IEEE Transactions on Image Processing. 2017. V. 26. N 3. P. 1466–1481. doi: 10.1109/TIP.2017.2651396

2. Olive D.J. Linear Regression. Springer, 2017. IX, 494 p. doi: 10.1007/978-3-319-55252-1

3. Xu J., Xu C., Zou B., Tang Y.Y., Peng J., You X. New incremental learning algorithm with support vector machines // IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2019. V. 49. N 11. P. 2230–2241. doi: 10.1109/TSMC.2018.2791511

4. Press S.J., Wilson S. Choosing between logistic regression and discriminant analysis // Journal of the American Statistical Association. 1978. V. 73. N 364. P. 699–705. doi: 10.1080/01621459.1978.10480080

5. Friedman J., Hastie T., Tibshirani R. Additive logistic regression: A statistical view of boosting // Annals of Statistics. 2000. V. 28. N 2. P. 337–407. doi: 10.1214/aos/1016218223

6. Subramaniyaswamy V., Logesh R. Adaptive KNN based recommender system through mining of user preferences // Wireless Personal Communications. 2017. V. 97. N 2. P. 2229–2247. doi: 10.1007/s11277-017-4605-5

7. Cheung D.W., Kao B., Lee J. Discovering user access patterns on the World Wide Web // Knowledge-Based Systems. 1998. V. 10. N 7. P. 463–470. doi: 10.1016/S0950-7051(98)00037-9

8. Liu D.-S., Fan S.-J. A modified decision tree algorithm based on genetic algorithm for mobile user classification problem // The Scientific World Journal. 2014. P. 468324.

9. Santra A., Jayasudha S. Classification of web log data to identify interested users using Naïve Bayesian classification // International Journal of Computer Science Issues (IJCSI). 2012. V. 9. N 1. P. 381.

10. Park S., Suresh N.C., Jeong B.-K. Sequence-based clustering for web usage mining: A new experimental framework and ann-enhanced k-means algorithm // Data & Knowledge Engineering. 2008. V. 65. N 3. P. 512–543. doi: 10.1016/j.datak.2008.01.002

11. Medina-Ortiz D., Contreras S., Quiroz C., Asenjo J.A., OliveraNappa Á. DMAKit: A user-friendly web platform for bringing stateof-the-art data analysis techniques to non-specific users // Information Systems. 2020. V. 93. P. 101557. doi: 10.1016/j.is.2020.101557

12. Meroño-Peñuela A. Refining Statistical Data on the Web. CreateSpace Independent Publishing Platform, 2016. 252 p.

 13. Nithya P., Sumathi P. Novel pre-processing technique for web log mining by removing global noise and web robots // Proc. of the National Conference on Computing and Communication Systems (NCCCS 2012). 2012. P. 41–45. doi: 10.1109/NCCCS.2012.6412976

14. Kanungo T., Mount D.M., Netanyahu N.S., Piatko C.D., Silverman R., Wu A.Y. An efficient k-means clustering algorithm: Analysis and implementation // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002. V. 24. N 7. P. 881–892. doi: 10.1109/TPAMI.2002.1017616

15. Yang S.-L., Li Y.-S., Hu X.-X., Pan R.-Y. Optimization study on k value of k-means algorithm // Xitong Gongcheng Lilun yu Shijian/ System Engineering Theory and Practice. 2006. V. 26. N 2. P. 97–101. (in Chinese)

16. Syakur M., Khotimah B., Rochman E.M.S., Satoto B.D. Integration k-means clustering method and elbow method for identification of the best customer profile cluster // IOP Conference Series: Materials Science and Engineering. 2018. V. 336. N 1. P. 012017. doi: 10.1088/1757-899X/336/1/012017

17. Thinsungnoen T., Kaoungku N., Durongdumronchai P., Kerdprasop K., Kerdprasop N. The clustering validity with silhouette and sum of squared errors // Proc. 3rd International Conference on Industrial Application Engineering (ICIAE 2015). 2015. P. 44–51. doi: 10.12792/iciae2015.012

18. Menardi G. Density-based Silhouette diagnostics for clustering methods // Statistics and Computing. 2011. V. 21. N 3. P. 295–308. doi: 10.1007/s11222-010-9169-0

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License